package org.example;

public class Test3 {
    //leetcode 538 把二叉树转换为累加树 https://leetcode.cn/problems/convert-bst-to-greater-tree/
    public int sum;
    public TreeNode convertBST(TreeNode root) {
        convertBSTChild(root);
        return root;
    }

    public void convertBSTChild(TreeNode root) {
        if (root == null) return;
        convertBSTChild(root.right);
        root.val += sum;
        sum = root.val;
        convertBSTChild(root.left);
    }

//    public TreeNode convertBSTChild(TreeNode root, int prev) {
//        if (root == null) return null;
//        root.right = convertBSTChild(root.right,prev);
//        if (prev != root.val) {
//            root.val += prev;
//        }
//        prev = root.val;
//        root.left = convertBSTChild(root.left,prev);
//        return root;
//    }
//
//    public int convertBSTChild(TreeNode root) {
//        if (root == null) return 0;
//        int rightRet = convertBSTChild(root.right);
//        root.val += rightRet;
//
//    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(0);
        TreeNode b = new TreeNode(1);
        TreeNode c = new TreeNode(2);
        TreeNode d = new TreeNode(3);
        TreeNode e = new TreeNode(4);
        TreeNode f = new TreeNode(5);
        TreeNode g = new TreeNode(6);
        TreeNode h = new TreeNode(7);
        TreeNode i = new TreeNode(8);
        e.left = b;
        e.right = g;
        b.left = a;
        b.right = c;
        c.right = d;
        g.left = f;
        g.right = h;
        h.right = i;
        Test3 test3 = new Test3();
        test3.convertBST(e);
        System.out.println(999);
    }
}
